package com.epam;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {

	public static void main(String[] args) {
		
		QuickSort quickSort = new QuickSort();
		
		quickSort.initArray(20);
		System.out.println(Arrays.toString(quickSort.array));
		quickSort.sort();
		System.out.println(Arrays.toString(quickSort.array));
	}

	private int length;
	private int[] array;
	
	void initArray(int length) {
		this.length = length;
		array = new int[length];
		for (int i=0; i < length; i++) {
			array[i] = (new Random()).nextInt(100);
		}
	}

	
	public void sort() {
		int startIndex = 0;
		int endIndex = length - 1;
		sort(startIndex, endIndex);
	}

	private void sort(int start, int end) {
		if (start >= end)
			return;
		int i = start;
		int j = end;
		int current = i - (i - j) / 2;
		while (i < j) {
			while (i < current && (array[i] <= array[current])) {
				i++;
			}
			while (j > current && (array[current] <= array[j])) {
				j--;
			}
			if (i < j) {
				int temp = array[i];
				array[i] = array[j];
				array[j] = temp;
				if (i == current)
					current = j;
				else if (j == current)
					current = i;
			}
		}
		sort(start, current);
		sort(current + 1, end);
	}


}

